package de.hska.master.algo;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

import de.hska.master.model.Model;
import de.hska.master.model.Point;
import de.hska.master.support.Geometry;

/**
 * Implementation of the convexhull-problem solving algorithm by graham.
 */
public class GrahamAlgorithm {

	private Model model = null;
	private Geometry calculations = null;

	/**
	 * Creates a grahamalgo instance to calculate the convex-hull on the data of
	 * the model and make it visible via viewer.
	 * 
	 * @param model
	 *            data to calculate on
	 * @param viewer
	 *            shows data as a gui. may be null
	 */
	public GrahamAlgorithm(Model model) {
		super();
		this.model = model;
		this.calculations = new Geometry();
	}

	/**
	 * runs the grahamscan algorithm
	 * 
	 * @throws InterruptedException
	 */
	public Stack<Point> runAlgorithm() throws InterruptedException {
		// get point with the min y (min x) coordinates
		Point startPoint = getStartPoint();
		List<Point> points = model.getPointsAsList();
		points.remove(startPoint);

		// sort points with mergesort
		Collections.sort(points, new ComparableGrahamScan(startPoint));

		Stack<Point> stack = new Stack<Point>();
		stack.push(startPoint);
		stack.push(points.get(0));
		stack.push(points.get(1));

		int i = 2;
		while (i < points.size()) {
			if (isNotConvex(stack, points.get(i)) < 0) {
				stack.push(points.get(i));
				i++;
			} else {
				stack.pop();
			}
		}
		return stack;

	}

	private double isNotConvex(Stack<Point> stack, Point point) {

		if (stack.size() == 1) {
			return 1;
		}
		return calculations.crossProduct(point, stack.get(stack.size() - 2),
				stack.peek());

	}

	private Point getStartPoint() {
		Point[] points = model.getPoints();
		Point minPoint = points[0];
		for (int i = 1; i < points.length; i++) {
			if (points[i].getY() < minPoint.getY()) {
				minPoint = points[i];
			}
			if (points[i].getY() == minPoint.getY()) {
				if (points[i].getX() < minPoint.getX()) {
					minPoint = points[i];
				}
			}
		}
		return minPoint;
	}

	/**
	 * A customized comperator, to sort the points on the basis of the
	 * startelement.
	 * 
	 * @author julia
	 * 
	 */
	private class ComparableGrahamScan implements Comparator<Point> {
		private Point pivotelement;

		public ComparableGrahamScan(Point pivot) {
			this.pivotelement = pivot;
		}

		@Override
		public int compare(Point o1, Point o2) {
			double crossProduct = calculations.crossProduct(o1, pivotelement,
					o2);
			if (crossProduct > 0) {
				return -1;
			} else {
				return 1;
			}
		}
	}

}
